package interview.s2020s;

import java.util.Scanner;

/**
 * 小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩
 *
 * 对于字符串中连续的m个相同字符串S将会压缩为 [m|S] (m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？
 *
 * 输入描述:
 * 输入第一行包含一个字符串s，代表压缩后的字符串。
 * S的长度<=1000;
 * S仅包含大写字母、[、]、|;
 * 解压后的字符串长度不超过100000;
 * 压缩递归层数不超过10层;
 *
 * 输出描述:
 * 输出一个字符串，代表解压后的字符串。
 *
 * 输入样例:
 * HG[3|B[2|CA]]F
 * 输出样例:
 * HGBCACABCACABCACAF
 */
public class 压缩算法 {

    private static String uncompress(String s){
        if (s.indexOf('[') == -1){
            return s;
        }else{
            StringBuilder sb = new StringBuilder();
            int a = s.indexOf('[');
            sb.append(s, 0, a);

            while (a != -1){
                int b = getCompressStringRight(s, a);

                String tmp = s.substring(a+1, b);
                int sf = tmp.indexOf('|');
                int n = Integer.parseInt(tmp.substring(0, sf));
                for (; n > 0; n--){
                    sb.append(uncompress(tmp.substring(sf+1)));
                }
                a = s.indexOf('[', b);
                if (a != -1 && b+1 != a) sb.append(s.substring(b+1, a));
                else if (a==-1 && b+1 <= s.length()-1) sb.append(s.substring(b+1));
            }
            return sb.toString();
        }
    }

    private static int getCompressStringRight(String s, int a){
        int l = 1;
        int r = 0;
        for (int i = a+1; i < s.length(); i++){
            if (s.charAt(i) == '[') l++;
            if (s.charAt(i) == ']') r++;
            if (l == r) return i;
        }
        return -1;
    }

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        System.out.println("请输入压缩字符串：");
        while (sc.hasNextLine()){
            String s = sc.nextLine();
            if (s.equals("\n") || s.equals("")){
                System.out.println("请输入压缩字符串：");
            }else {
                System.out.println(uncompress(s));
            }
            System.out.println("请输入压缩字符串：");
        }
    }
}
